﻿// 0726train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <map>

using namespace std;

/*
输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

输入：s = "3[a2[c]]"
输出："accaccacc"


 */

string solve1(string s)
{
	string oh_str = s;
	stack<int>num_stack;
	stack<string>str_stack;
	int str_size = oh_str.size();

	int digit = 0;
	string result;

	for (int i=0; i<str_size; i++)
	{
		char curr_char = oh_str[i];
		if (curr_char>='0' && curr_char<='9')
		{
			int curr_digit = curr_char - '0';
			digit = digit * 10 + curr_digit;
		}
		else if (curr_char>= 'a' && curr_char <= 'z')
		{
			result += curr_char;
		}
		else if ('[' == curr_char)
		{
			num_stack.push(digit);
			str_stack.push(result);

			digit = 0;
			result = "";
			//此时，下一个i将是字符，或者[
		}
		else if (']' == curr_char)
		{
			int curr_digit = num_stack.top();
			num_stack.pop();

			string prev_str = str_stack.top();
			str_stack.pop();

			//左括号里面的字符，目前记录在result上面
			for (int i=0; i < curr_digit; i++)
			{
				prev_str += result;
			}

			//重置result
			result = prev_str;

		}

		//for------
		//------
	}
	return result;
}



/*
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），
请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；
此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；
两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。
对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠 '/' 开头。
- 两个目录名之间必须只有一个斜杠 '/' 。
- 最后一个目录名（如果存在）不能 以 '/' 结尾。
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 
示例 2：
输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
示例 3：
输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：path = "/a/./b/../../c/"
输出："/c"
提示：
- 1 <= path.length <= 3000
- path 由英文字母，数字，'.'，'/' 或 '_' 组成。
- path 是一个有效的 Unix 风格绝对路径。

https://leetcode.cn/problems/simplify-path/
 */

string solve2(string path)
{
	string oh_str = path;
	stack<char>oh_stack;
	int str_size = oh_str.size();
	string result;

	bool is_pop = false;
	for (int i=0; i < str_size; i++)
	{
		char curr_char = oh_str[i];

		if (curr_char == '/')
		{
			is_pop = false;
			if (oh_stack.empty())
			{
				result += '/';
				oh_stack.push('/');
			}
			else
			{
				oh_stack.pop();
			}
		}

		else if (curr_char>='a' && curr_char<='z')
		{
			//出现英文就pop前面存的/
			if (!is_pop && !oh_stack.empty())
			{
				oh_stack.pop();
				is_pop = true;
			}
			result += curr_char;
		}

		else if (curr_char=='.')
		{
			//出现 . 全部重置
			result = "";
			if (!oh_stack.empty())
			{
				oh_stack.pop();
			}
		}

		//for------
		//------
	}

	if (result.size()==1)
	{
		return result;
	}

	stack<char>result_stack;
	for (auto& item : result)
	{
		result_stack.push(item);
	}
	while (!result_stack.empty() && result_stack.top() == '/')
	{
		result_stack.pop();
	}

	string stack_str;
	while (!result_stack.empty())
	{
		stack_str += result_stack.top();
		result_stack.pop();
	}
	//cout << stack_str;
	reverse(stack_str.begin(), stack_str.end());
	result = stack_str;

	return result;
}


string solve22(string path)
{
	string oh_str = path;
	stringstream oh_sstream(oh_str);
	string token;
	vector<string>path_name_vec;
	while (getline(oh_sstream, token, '/'))
	{
		path_name_vec.push_back(token);
	}

	vector<string>oh_stack_vec;
	int path_vec_size = path_name_vec.size();
	for (int i=0; i<path_vec_size; i++)
	{
		string name = path_name_vec[i];
		if (name== ".." && !oh_stack_vec.empty())
		{
			oh_stack_vec.pop_back();
		}
		else if (!name.empty()&& name != "." && name != "..")
		{
			oh_stack_vec.push_back(name);
		}
		//for------
		//------
	}

	stringstream result_sstream;
	int stack_size = oh_stack_vec.size();
	result_sstream << "/";
	for (int i=0; i<stack_size; i++)
	{
		if (i!= stack_size-1)
		{
			result_sstream << oh_stack_vec[i] << "/";
		}
		else
		{
			result_sstream << oh_stack_vec[i];
		}
	}


	string result = result_sstream.str();
	return result;
}


/*
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入
push 和弹出 pop 操作序列的结果时，返回 true；否则，返回false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
 */

bool solve33(vector<int>pushed, vector<int>popped)
{
	stack<int>oh_stack;
	int pop_index = 0;

	for (int i=0; i < pushed.size(); i++)
	{
		
		int curr_val = pushed[i];
		oh_stack.push(curr_val);

		while (!oh_stack.empty() && oh_stack.top() == popped[pop_index])
		{
			oh_stack.pop();
			pop_index++;
			
		}

	}
	return oh_stack.empty();
}


int main()
{
	{
		vector<int>pushed = { 1,2,3,4,5 };
		vector<int>popped = { 4,5,3,2,1 };

		cout << solve33(pushed, popped);

		return 0;
	}


	{
		/*
		输入：path = "/home/"
		输出："/home"

		输入：path = "/../"
		输出："/"

		输入：path = "/home//foo/"
		输出："/home/foo"
		 */
		string path = "/../";
		cout << solve22(path);
		return 0;
	}

	/*
	 * 输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

输入：s = "3[a2[c]]"
输出："accaccacc"
	 */

	cout << solve1("3[a2[c]]");
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
